Java 源码学习之java.util.ArrayList

文章目录

1. 构造函数
2. add和扩容
3. remove部分
4. Iterator部分
5. 其他的一些便利api
6. 总结：

ArrayList是Java编程中最常用的容器类之一，它是基于动态的数组实现的，在面试时常常被与Vector、LikedList作比较！

本文将主要从ArrayList的构造函数、add、remove,iterator为入口进行源码分析

构造函数

在看构造函数之后先看下一下ArrayList类的三个重要私有变量

/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to
 * DEFAULT_CAPACITY when the first element is added.
 */
private transient Object[] elementData;

/**
 * The size of the ArrayList (the number of elements it contains).
 *
 * @serial
 */
private int size;

从注释中很容易了解到：

DEFAULT_CAPACITY为ArrayList的默认容量，大小为10，
elementData就是为存储ArrayList的实体数组，注意它是transient的，也就是在进行序列化的时候不会被持久化，另一个要点他是Object类型的，也就是ArrayList存储数据时会进行装箱和拆箱操作
size为ArrayList存储的实际容量，这个值在执行add方法可能会有扩容的操作

咱们在来看一下ArrayList的构造函数

/**
 * Constructs an empty list with the specified initial capacity.
 *
 * @param  initialCapacity  the initial capacity of the list
 * @throws IllegalArgumentException if the specified initial capacity
 *         is negative
 */
public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
}

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    super();
    this.elementData = EMPTY_ELEMENTDATA;
}

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    size = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}

ArrayList在进行实例时其实就是实例化elementData数组变量，他可以指定数组的大小，如果未指定就使用默认的DEFAULT_CAPACITY，它还可以直接使用集合类的数据直接进行初始化

add和扩容

add方法是咱们在ArrayList上最为常用的一个方法，先来看下Java中对add方法的定义

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;//对实体数组进行赋值，同时将ArrayList的实际尺寸累加1
    return true;
}

add方法在java中定义极为精简，一眼看过去就是在实体数组中进行相应索引位置的赋值以及size变量的累加，但是各位请注意一下ensureCapacityInternal这个方法

/**
 * Increases the capacity of this <tt>ArrayList</tt> instance, if
 * necessary, to ensure that it can hold at least the number of elements
 * specified by the minimum capacity argument.
 *
 * @param   minCapacity   the desired minimum capacity
 */
public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != EMPTY_ELEMENTDATA)
        // any size if real element table
        ? 0
        // larger than default for empty table. It's already supposed to be
        // at default size.
        : DEFAULT_CAPACITY;

    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);//这里调用扩容方法
}

该方法主要是在进行数组元素赋值前进行数组的容量“确保”，防止其越界，当然当前添加元素之后如果所需数组容量大于size，它就会进行扩容操作：

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);//扩容，每次增长oldLength/2
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);//每次扩容都会将原有的数组重新拷贝一份
}

数组扩容方法中有两个较为重要的点：

每次扩容时都是增加原数组大小的一半（这也是面试中较为常问的一个点）
他是使用数组的拷贝来完成扩容的，这里将会产生较大的开销，不过还好的是调用的拷贝方法Arrays.copyOf最终是调用System.arraycopy，它是一个native方法

ArrayList的add方法大致就是按照上述实现的，其余的addAll,add(index,e)方法也基本都是调用上述的方法来完成的

remove部分

remove方法主要有根据数组索引或者数组的值进行删除这两种方法，还是先看源码

/**
 * Removes the element at the specified position in this list.
 * Shifts any subsequent elements to the left (subtracts one from their
 * indices).
 *
 * @param index the index of the element to be removed
 * @return the element that was removed from the list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

/**
 * Removes the first occurrence of the specified element from this list,
 * if it is present.  If the list does not contain the element, it is
 * unchanged.  More formally, removes the element with the lowest index
 * <tt>i</tt> such that
 * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
 * (if such an element exists).  Returns <tt>true</tt> if this list
 * contained the specified element (or equivalently, if this list
 * changed as a result of the call).
 *
 * @param o element to be removed from this list, if present
 * @return <tt>true</tt> if this list contained the specified element
 */
public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

/*
 * Private remove method that skips bounds checking and does not
 * return the value removed.
 */
private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

remove方法大致可以有如下几种归纳：

remove(index)会进行index的越界检查，在进行移除时是使用数组拷贝来完成的，在移除完成之后方法会返回被移除的值
remove(obj)根据obj是否为null分为两种情况考虑，主要是使用相等的方式不同==和equal
remove(obj)会调用fastRemove来完成移除操作，而fastRemove也是使用数组的拷贝来完成的
在remove时会将size递减1，所以在ArrayList的循环中删除元素时需要小心，较为安全的方法在ArrayList的Iterator部分提及

Iterator部分

ArrayList实现他的迭代器，可以使用foreach进行循环遍历

/**
 * An optimized version of AbstractList.Itr
 */
private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];//将当前的i赋值给lastRet  并且返回elementData[lastRet]数组的值
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

它的迭代器实现较为精简，主要是实现了next和remove两个方法，其实这里的remove可以完成我们在迭代过程中进行元素的移除，不过由于有lastRet < 0的检测，所以必须在进行next之后才能进行调用remove方法，不然会报错

例如：

ArrayList<Integer> list=new ArrayList<Integer>(Arrays.asList(1,2,3,4,5));
Iterator<Integer> iter=list.iterator();
while(iter.hasNext())
{
	if(iter.next()==3)//先执行next
	{
		iter.remove();//再用remove就ok了
	}
}
System.out.println(list);//会打印[1, 2, 4, 5]

其他的一些便利`api`

ArrayList提供了丰富的api，例如

indexOf：元素的索引位置查找O(N)
fill：元素的填充
contains：元素的查找等，会调用indexOf
get：直接使用数组索引取值O(1)
toArray：转为数组

总结：

ArrayList是基于动态数组实现的
在使用add方法时遇到容量不够会执行扩容操作，每次增加原数组的一半，需要使用数组拷贝完成，所以使用ArrayList尽量指定所需要的容量
在迭代删除元素时先next，再remove
ArrayList的取值方法是O(1)，查找方法是O(N)，在插入元素时如果不需要扩容也是O(1)，如果扩容就有较大开销

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。

Kubi Code'Blog

The palest ink is better than the best memory.

Java 源码学习之java.util.ArrayList

构造函数

add和扩容

remove部分

Iterator部分

其他的一些便利`api`

总结：

构造函数

add和扩容

remove部分

Iterator部分

其他的一些便利api

总结：

其他的一些便利`api`